#include "stdafx.h"

namespace cpputils
{

void binomial_batch_calculator::clear()
{
	reset_vector(Data);
}

double binomial_batch_calculator::operator()(int N, int M)
{
	if (N < 0 || M < 0 || M > N) return 0;
	while ((int)Data.size() <= N) add_line();
	return Data[N][M];
}

void binomial_batch_calculator::add_line()
{
	if (Data.empty())
	{
		Data.resize(1);
		Data[0].assign(1, 1);
		return;
	}
	int N = Data.size();
	Data.resize(N + 1);
	Data[N].resize(N + 1);
	Data[N][0] = Data[N][N] = 1;
	for (int I = 1; I < N; I++) Data[N][I] = Data[N - 1][I - 1] + Data[N - 1][I];
}

vector<int> decompose_primes(int N)
{
	vector<int> P;
	for (int I = 2; I * I <= N; I++)
		while (N % I == 0)
			P.push_back(I), N /= I;
	if (N > 1) P.push_back(N);
	return P;
}

double compute_binomial(int N, int M)
{
	if (N - M > M) M = N - M;
	vector<int> PN, PM;
	for (int I = M + 1; I <= N; I++)
	{
		vector<int> Temp = decompose_primes(I);
		PN.insert(PN.begin(), Temp.begin(), Temp.end());
	}
	for (int I = 1; I <= N - M; I++)
	{
		vector<int> Temp = decompose_primes(I);
		PM.insert(PM.begin(), Temp.begin(), Temp.end());
	}
	sort(PN.begin(), PN.end());
	sort(PM.begin(), PM.end());
	int Cur = 0;
	double Result = 1;
	for (int I = 0; I < (int)PN.size(); I++)
		if (Cur < (int)PM.size() && PM[Cur] == PN[I]) Cur++;
		else Result *= PN[I];
	return Result;
}

}
